package com.sx.sx1.lintcode.day717;

public class LC439 {


      static class SegmentTreeNode {
          public int start, end, max;
          public SegmentTreeNode left, right;
          public SegmentTreeNode(int start, int end, int max) {
              this.start = start;
              this.end = end;
              this.max = max;
              this.left = this.right = null;
          }

          @Override
          public String toString() {
              return start+"_"+ end;
          }
      }


    static class Solution {
        /**
         * @param a: a list of integer
         * @return: The root of Segment Tree
         */
        public SegmentTreeNode build(int[] a) {
            if(a ==null || a.length ==0)
                return null;

            return f(a,0,a.length-1);
        }

        public SegmentTreeNode f(int[] arr,int start,int end){
            if(start ==end){
                return new SegmentTreeNode(start,end,arr[start]);
            }
            SegmentTreeNode root = new SegmentTreeNode(start,end,Integer.MIN_VALUE);
            int m = start+(end-start)/2;
            root.left = f(arr,start,m);
            root.right = f(arr,m+1,end);
            root.max=Math.max(root.left.max,root.right.max);
            return root;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        TreeNodeShow.show(obj.build(new int[]{3,2,1,4}));
    }


    //打印二叉树的类
    // TreeOperation.java
    static class TreeNodeShow {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

        // 用于获得树的层数
        public static int getTreeDepth(SegmentTreeNode root) {
            return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
        }


        private static void writeArray(SegmentTreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
            // 保证输入的树不为空
            if (currNode == null) return;
            // 先将当前节点保存到二维数组中
            String nodevs1 = currNode.start+","+ currNode.end+"|"+ currNode.max;
            String nodevs =  currNode.max+"";
            res[rowIndex][columnIndex] = String.valueOf(nodevs);

            // 计算当前位于树的第几层
            int currLevel = ((rowIndex + 1) / 2);
            // 若到了最后一层，则返回
            if (currLevel == treeDepth) return;
            // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
            int gap = treeDepth - currLevel - 1;

            // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
            if (currNode.left != null) {
                res[rowIndex + 1][columnIndex - gap] = "/";
                writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
            }

            // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
            if (currNode.right != null) {
                res[rowIndex + 1][columnIndex + gap] = "\\";
                writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
            }
        }


        public static void show(SegmentTreeNode root) {
            if (root == null) System.out.println("EMPTY!");
            // 得到树的深度
            int treeDepth = getTreeDepth(root);

            // 最后一行的宽度为2的（n - 1）次方乘3，再加1
            // 作为整个二维数组的宽度
            int arrayHeight = treeDepth * 2 - 1;
            int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
            // 用一个字符串数组来存储每个位置应显示的元素
            String[][] res = new String[arrayHeight][arrayWidth];
            // 对数组进行初始化，默认为一个空格
            for (int i = 0; i < arrayHeight; i++) {
                for (int j = 0; j < arrayWidth; j++) {
                    res[i][j] = " ";
                }
            }

            // 从根节点开始，递归处理整个树
            // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
            writeArray(root, 0, arrayWidth / 2, res, treeDepth);

            // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
            for (String[] line : res) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < line.length; i++) {
                    sb.append(line[i]);
                    if (line[i].length() > 1 && i <= line.length - 1) {
                        i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                    }
                }
                System.out.println(sb.toString());
            }
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有181条未读消息，请及时查看
439 · 线段树的构造 II
算法
中等
通过率
48%

题目
题解6
笔记
讨论77
排名
记录
描述
线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:

根节点的 start 和 end 由 build 方法所给出。
对于节点 A 的左儿子，有 start=A.left, end=(A.left + A.right) / 2。
对于节点 A 的右儿子，有 start=(A.left + A.right) / 2 + 1, end=A.right。
如果 start 等于 end, 那么该节点是叶子节点，不再有左右儿子。
对于给定数组实现build方法, 线段树的每个节点储存区间最大值, 返回根节点.

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


线段树(又称区间树)是一种高级数据结构, 支持一系列区间查询/修改操作.

维基百科: https://zh.wikipedia.org/zh-hans/%E7%B7%9A%E6%AE%B5%E6%A8%B9

样例
输入: [3,2,1,4]
解释:
这颗线段树将会是
          [0,3](max=4)
          /          \
       [0,1]         [2,3]
      (max=3)       (max=4)
      /   \          /    \
   [0,0]  [1,1]    [2,2]  [3,3]
  (max=3)(max=2)  (max=1)(max=4)
标签
相关题目

201
线段树的构造
中等
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
已开启智能提示
发起考试
30 分 00 秒
1234567891011121314151617181920212223
        // write your code here
    }
}
控制台
历史提交

 */
